package binary_tree.sort.LeetCode;

import java.util.*;

public class Num347 {
    private class Freq{
        //出现的数字
        int key;
        //数字出现的次数
        int freq;

        public Freq(int key,int freq) {
            this.key = key;
            this.freq=freq;
        }
    }
    public int[] topKFrequent(int[] nums, int k) {
        //1.先扫描原数组，将出现的元素以及元素出现次数保存下来
        Map<Integer,Integer> map=new HashMap<>();
        for(int i:nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
            if (map.containsKey(i)) {
                     int value=map.get(i);
                     map.put(i,value+1);
            }   else{
                map.put(i,1);
            }
        }
        //2.扫描Map把前k个出现的元素key，以及出现的次数放入优先级队列中
        // 堆使用的是最小堆（因为要求的是前k个出现次数最多的元素，所以使用最小堆存储）
        //向优先级中传入一个比较器，比较的是freq对象的value值的大小，o1-o2
        PriorityQueue<Freq> queue=new PriorityQueue<>(new Comparator<Freq>() {
            @Override
            //o1-o2是最小堆，o2-o1是最大堆
            public int compare(Freq o1, Freq o2) {
                return o1.freq- o2.freq;
            }
        }) ;
        //3.map集合的遍历
        //每个entry存储了出现的元素(key)和元素出现的个数(value)
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            if(queue.size()<k){
                queue.offer(new Freq(entry.getKey(),entry.getValue()));
            } else{
                Freq peekFreq= queue.peek();
                if(entry.getValue()> peekFreq.freq){
                    queue.poll();
                    queue.offer(new Freq(entry.getKey(),entry.getValue()));
                }
            }
        }
        int[] ret=new int[k];
        for(int i=0;i<k;i++){
                 ret[i]=queue.poll().key;
        }
        return ret;
    }
}
        //第二种方法是使用循环入map，再map.put所对应的值的索引。
//        HashMap<Integer,Integer> map=new HashMap<>();
//        for(int i:nums){
//            if(map.containsKey(i)){
//                map.put(i, map.get(i)+1);
//            }else{
//                map.put(i,1);
//            }
//        }
//        PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return map.get(o1)-map.get(o2);
//            }
//        });
//        //构建最小堆
//        for(Integer key: map.keySet()){
//            if(queue.size()<k){
//                queue.add(key);
//            }else if(map.get(key)> map.get(queue.peek())){
//                queue.remove();
//                queue.add(key);
//            }
//        }
//        int[] res=new int[k];
//       for(int i=0;i<k;i++){
//           res[i]=queue.poll();
//       }
//        return res;


       //第一种方法：使用getOrDefault方法进行映射
//    int[] res=new int[k];
//    HashMap<Integer,Integer> map=new HashMap<>();
//    for(int i:nums){
//        map.put(i,map.getOrDefault(i,0)+1);
//    }
//    Set<Map.Entry<Integer,Integer>> entries= map.entrySet();
//    PriorityQueue<Map.Entry<Integer,Integer>> queue=new PriorityQueue<>(((o1, o2) ->o1.getValue()-o2.getValue() ));
//    for(Map.Entry<Integer,Integer> entry:entries){
//        queue.offer(entry);
//        if(queue.size()>k){
//            queue.poll();
//        }
//    }
//    for(int i=k-1;i>0;i--){
//        res[i]=queue.poll().getKey();
//    }
//    return res;

